7.28 When implementing quicksort, if the array contains lots of duplicates, it may be better to perform a three-way partition (into elements less than, equal to, and greater than the pivot), to make smaller recursive calls. Assume three-way comparisons, as provided by the compareTo method. a. Give an algorithm that performs a three-way in-place partition of an N-element subarray using only N − 1 three-way comparisons. If there are d items equal to the pivot, you may use d additional Comparable swaps, above and beyond the two-way partitioning algorithm. (Hint: As i and j move toward each other, maintain five groups of elements as shown below): EQUAL SMALL UNKNOWN LARGE EQUAL i j b. Prove that using the algorithm above, sorting an N-element array that contains only d different values, takes O(dN) time. - Get 7.28a Solution / Sol. 7.28. b. Not available 7.29 Not Available | |
| View Solution | |
| << Back | Next >> |